#include <iostream>
#include <string>

using namespace std;

// 使用了新的数组进行操作
string reverseWords(string s) {
    string result {};
    int idx {};
    for (int i = s.size() - 1; i >= 0; i--) {
        if (s[i] == ' ') {
            continue;
        }

        int right { i };
        while (i - 1 >= 0 && s[i - 1] != ' ') {
            i--;
        }
        int left { i };
        for (int j { left }; j <= right; j++) {
            cout << j << ": " << s[j] << "\n";
            // result[idx++] = s[j];
            result += s[j];
        }
        // result[idx++] = ' ';
        result += ' ';
    }

    // erase 操作时间复杂度为 O(n)
    result.erase(result.size() - 1, 1);
    
    return result;
}



// 类似数组的双指针删除元素
void removeExtraSpaces(string& s) {
    int slow {};
    for (int i{}, len = s.size(); i < len; i++) {
        if (s[i] == ' ') {

        } else {
            // 补上单词间的空格
            if (slow != 0) {
                s[slow++] = ' ';
            }
            // 把单词填上，遇到空格结束
            while (i < s.size() && s[i] != ' ') {
                s[slow++] = s[i++];
            }
        }
    }
    s.resize(slow);
}

// 左闭右闭
void reverse(string& s, int start, int end) {
    while (start < end) {
        swap(s[start++], s[end--]);
    }
}

/**
 * 思路：
 *   1.移除多余空格
 *   2.字符串反转
 *   3.单词反转
 */

// resize 可以用来修改字符串长度
string reverseWords2(string s) {
    removeExtraSpaces(s);
    reverse(s, 0, s.size() - 1);
    int start{};
    for (int i{}, len = s.size(); i <= len; i++) {
        // s[100] 超过长度取值为 NULL，并不会报错
        if (s[i] == ' ' || i == len) {
            reverse(s, start, i - 1);
            start = i + 1;
        }
    }
    
    return s;
}

int main() {
    string s { " asdasd df f" };
    cout << "origin: " << s << "\n";
    // reverse(s, 0, s.size() - 1);
    cout << "after: " << s << "end" << "\n";

    cout << "after2: " << reverseWords2(s) << "\n";
    
    return 0;
}